package week_02;

import java.util.*;

public class PermuteNums_46_2 {
    public static List<List<Integer>> ans;
    public static List<Integer> subset;
    public static int[] nums;
    public static boolean[] isUsed;
    public static Set<String> uniq;

    public List<List<Integer>> permute(int[] nums) {
        // dfs 深搜 遍历所有可能性
        ans = new ArrayList<>();
        subset = new ArrayList<>();
        uniq = new HashSet<>();
        this.nums = nums;
        //状态表确定数字i是否被用到
        this.isUsed = new boolean[nums.length];
        dfs(0);
        return ans;
    }

    public void dfs(int index) {
        if (index == nums.length) {
            String key = getHashKey(subset);
            if(!uniq.contains(key)){
                uniq.add(key);
                ans.add(new ArrayList<>(subset));
            }
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (isUsed[i]) {
                continue;
            } else {
                isUsed[i] = true;
                subset.add(nums[i]);
                dfs(index + 1);
                isUsed[i] = false;
                subset.remove(subset.size() - 1);
            }
        }
    }

    public String getHashKey(List<Integer> list) {
        StringBuffer sb = new StringBuffer();
        for(Integer integer:list){
            sb.append(sb).append("-");
        }
        return sb.toString();
    }

}
